Binary Tree
Q21.
Consider the following New-order strategy for traversing a binary tree: Visit the root; Visit the right sub tree using New-order; Visit the left sub tree using New-order; The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:Q22.
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.Q25.
Consider rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of sub trees having exactly 4 nodes is O(n^{a}lob^{b}n) . Then the value of a+10b is_______Q26.
A binary tree T has 20 leaves. The number of nodes in T having two children is _______.Q27.
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.Q28.
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root. int height (treeptr n) { if (n == NULL) return -1; if (n \rightarrow left == NULL) if (n \rightarrow right == NULL) return 0; else return B1; else { h1 = height (n \rightarrow left); if (n \rightarrow right == NULL) return (1+h1); else { h2 = height (n \rightarrow right); return B2; } } } The appropriate expressions for the two boxes B1 and B2 areQ30.
A binary tree with n>1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n_{3} can be expressed as